package offer;

/**
 * Creared with IntelliJ IDEA.
 * Description:输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。
 * User:yxd
 * Date:2022-07-17
 * Time:19:53
 */
import java.util.*;
class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
public class JZ35 {
    public RandomListNode Clone(RandomListNode pHead) {
        //空节点直接返回
        if(pHead == null)
            return pHead;
        //添加一个头部节点
        RandomListNode res = new RandomListNode(0);
        //哈希表，key为原始链表的节点，value为拷贝链表的节点
        HashMap<RandomListNode, RandomListNode> mp = new HashMap<>();
        RandomListNode cur = pHead;
        RandomListNode pre = res;
        //遍历原始链表，开始复制
        while(cur != null){
            //拷贝节点
            RandomListNode clone = new RandomListNode(cur.label);
            //用哈希表记录该节点下的拷贝节点
            mp.put(cur, clone);
            //连接
            pre.next = clone;
            pre = pre.next;
            //遍历
            cur = cur.next;
        }
        //遍历哈希表
        for(HashMap.Entry<RandomListNode, RandomListNode> entry : mp.entrySet()){
            //原始链表中random为空
            if(entry.getKey().random == null)
                entry.getValue().random = null;
            else
                //将新链表的random指向哈希表中原始链表的random
                entry.getValue().random = mp.get(entry.getKey().random);
        }
        //返回去掉头
        return res.next;
    }
}
